## Алгоритмы поиска на графах 

* Поиск в ширину.
* Поиск в глубину.
* Поиск кратчайшего пути

* _Алгоритм Дейкстры_
* _Жадные алгоритмы_


Актуальность 

![](img/metro.png)

![](img/graph-1.png)


![](img/graph-2.png)


![](img/graph-3.png)


![](img/graph-4.png)


![](img/graph-5.png)


![](img/graph-6.png)

### Задача 
Сколько существует способов попасть из числа 3 в число 6, используя три команды, которым: 

* Прибавить 1, 
* Прибавить 2 или 
* Умножить на 2

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2. 

Построить граф траекторий вычислений


![](img/graph-7.png)

Сколько существует способов попасть из числа 3 в число 20, используя три команды, которым:

### Задача 

* Прибавить 1, 
* Прибавить 2 
* При этом траектория вычислений содержит число 9 и не содержит числа 15


## Что такое граф?


`Граф` – это конечное множество вершин (или узлов) и множество ребер, соединяющих эти вершины.
 


![](img/types_graphs.png)

Две вершины называются `соседними`, если они соединены друг с другом ребром. 


`Путь` – последовательность вершин, в которой каждая вершина соединена со следующей вершиной ребром. 

На рисунке красными стрелками показан путь от `1` к `3` через `4`.

* `Порядок` – количество вершин графа.
* `Размер` – количество ребер графа.
* `Связность` (степень связности) вершины – количество ребер, исходящих из этой вершины.
* `Изолированная вершина` – вершина, не связанная с другими вершинами графа.

* `Петля` – ребро от вершины к этой же вершине.
* `Ориентированный граф` – граф, в котором все ребра имеют направление, указывающее, какая из вершин ребра является начальной, а какая – конечной.
* `Неориентированный граф` – граф, в котором у ребер нет направлений.
* `Взвешенный граф` – все ребра графа имеют веса.
* `Невзвешенный граф` – ребра графа не имеют весов.

## Примеры ориентированных графов

#### Вертикальная структура управления 
![](img/orient_graph.png)

#### Последовательность фибоначи

![](img/fib.png)


### Полный граф и сеть

![](img/full_graph.png)

## ? сколько ребер в графе с 4 вершинами

## сколько ребер в полном графе с 9 вершинами

> (n=p (p-1)/2, где р – количество вершин)

### Путь в графе

![](img/path_graph.png)

### Цикл в графе

![](img/cycle_graph.png)


### Связный граф и компонента связности

![](img/linked_graph.png)


## Алгоритмы поиска на графах

![](img/alg_graph.png)

![](img/alg_graph_1.png)

![](img/alg_graph_2.png)

![](img/deq_graph.png)

## Поиск в глубину (DFS)

![](img/dfs-1.png)

Поиск `DFS(Depth-First Search)` в глубину используется:

* для нахождения пути между двумя вершинами;
* для обнаружения циклов в графе;
* для решения головоломок, имеющих только одно решение (например, лабиринтов).


Позволяет построить обход ориентированного или неориентированного графа,
при котором посещаются все вершины, доступные из начальной вершины.

### Алгоритм обхода в глубину:

1. Пойти в какую-нибудь смежную вершину, не посещенную ранее.
2. Запустить из этой вершины алгоритм обхода в глубину
3. Вернуться в начальную вершину.
4. Повторить пункты 1-3 для всех не посещенных ранее смежных вершин.

```
#         3 --5--2   6--7
#        / \ /  /
#       0---1--4
```


```python
graph = [
    # список смежности
    [1, 3],         # 0
    [0, 3, 4, 5],   # 1
    [4, 5],         # 2
    [0, 1, 5],      # 3
    [1, 2],         # 4
    [1, 2, 3],      # 5
    [7],            # 6
    [6]             # 7
]

visited = [False] * (len(graph))
start = 0


def dfs(v):
    visited[v] = True
    for w in graph[v]:
        if not visited[w]:  # посещён ли текущий сосед?
            dfs(w)


dfs(start)

print(visited)

```

### Таблица смежности


```python
graph = {
    1: {1, 2, 3, 4, 5},
    2: {1, 6, 7},
    3: {1, 8},
    4: {1},
    5: {1},
    6: {2},
    7: {2},
    8: {3},
}
```

Алгоритм

```python
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited
res = dfs(graph, 1)
```

Можно проще

```python
visited = [False] * (len(graph))
start = 0

def dfs(v):
    visited[v] = True
    for w in graph[v]:
        if not visited[w]:
            dfs(w)

dfs(start)
print(visited)

```

### Задача. Нахождение пути сквозь лабиринт

![](img/dfs_labirint.png)

### Делим лабиринт на зоны

![](img/dfs_labirint_2.png)

`Таблица смежности`


```python
graph = {
    1: {2},
    2: {1, 3},
    3: {2, 4},
    4: {3, 5, 8},
    5: {4, 6},
    6: {5, 7},
    7: {6},
    8: {4, 9},
    9: {8, 10},
    10: {9, 11},
    11: {10, 12},
    12: {11}
}
```

![](img/dfs_labirint_3.png)


### Нахождение конкретного пути с помощью DFS?

![](img/dfs_labirint_4.png)

## Поиск в ширину BFS (Breadth-First Search)

`Обход или поиск` – одна из основных операций, которую можно провести на графе. 

* При поиске в ширину мы начинаем с определенной вершины и исследуем всех ее соседей на том же уровне, прежде чем переходить к следующему уровню.

* В отличие от деревьев, графы могут содержать циклы (пути, в которых начальная и конечная вершины совпадают), так что нам придется отслеживать вершины, которые мы посетили. 

* Реализуя поиск в ширину, обычно используют структуру данных очередь.


![](img/bfs.png)

## Поиск в ширину используется:

* для обнаружения кратчайших путей и минимальных покрывающих деревьев;
* поисковыми системами для построения индексов веб-страниц;
* для поиска в социальных сетях;
* для нахождения доступных соседних узлов в одноранговых сетях вроде BitTorrent.


### Граф смежности

![](img/dfs-1.png)


```python
#  BFS(Breadth-First Search). Алгоритм поиска в ширину.
# Позволяет найти кратчайшие расстояния из одной вершины невзвешенного (ориентированного или неориентированного) графа
# до всех остальных вершин.
# Под кратчайшим путем подразумевается путь, содержащий наименьшее число ребер.
# Алгоитм:
# 1. Начальную вершину помещаем в очередь
# 2. Пока очередь не пуста:
#   2.1 Достаем из очереди первую вершину
#   2.2 Для каждой вершины списка смежности
#       2.2.1 Если еще до этой вершины еще не доходили, то помечаем расстояние до нее и добавляем ее в конец очереди
#       2.2.1 Если вершину уэе посещали, то игнорируем ее
#         3 --5--2   6--7
#        / \ /  /
#       0---1--4
graph = [
    # список смежности
    [1, 3],         # 0
    [0, 3, 4, 5],   # 1
    [4, 5],         # 2
    [0, 1, 5],      # 3
    [1, 2],         # 4
    [1, 2, 3],      # 5
    [7],            # 6
    [6]             # 7
]

start = 0
lengths = [None] * (len(graph))
lengths[start] = 0
queue = [start]
while queue:
    cur_vertex = queue.pop(0)
    for vertex in graph[cur_vertex]:
        if lengths[vertex] is None:
            lengths[vertex] = lengths[cur_vertex] + 1
            queue.append(vertex)
     print(queue)
print(lengths)
```



![](img/bfs1.png)

```python
graph = {
    0: {1, 3},
    1: {0, 3, 4, 5},
    2: {4, 5},
    3: {0, 1, 5},
    4: {1, 2},
    5: {1, 2, 3},
    6: {7},
    7: {6}
}
```

### Адаптированный алгоритм BFS

```python
graph = [
    # список смежности
    [1, 3],  # 0
    [0, 3, 4, 5],  # 1
    [4, 5],  # 2
    [0, 1, 5],  # 3
    [1, 2],  # 4
    [1, 2, 3],  # 5
    [7],  # 6
    [6]  # 7
]

def bfs(graph, start, end):
    queue = [[start]]
    # queue.append()
    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node == end:
            return path
        # перебираем соседние узлы, создаем
        # новый путь и помещаем его в очередь
        for vertex in graph[node]:
            new_path = path.copy()
            new_path.append(vertex)
            queue.append(new_path)

print(bfs(graph, 0, 2))

```

### Задача. Снова лабиринт

![](img/dfs_labirint_4.png)

### Кратчайший путь


Кратчайший путь от одной вершины графа до другой – это путь, имеющий минимальный суммарный вес входящих в него ребер. 
На рисунке минимальный путь от вершины 1 к вершине 6

![](img/short_path.png)

#### Алгоритм Дейкстры поиска минимального пути

Поиск кратчайшего пути используется:

* для построения маршрута в приложениях Яндекс-картах, 2-ГИС, Google Maps;
* при создании компьютерных сетей – чтобы обеспечить минимальную задержку;
* в абстрактных автоматах для определения оптимальной стратегии достижения некоторой цели через несколько промежуточных состояний (например, для подсчета, сколько нужно ходов для победы в игре).


![](img/dijkstra.png)

```python
nodes = ('1', '2', '3', '4', '5', '6')
distances = {
    '1': {'2': 2, '3': 5},
    '2': {'4': 6, '5': 10},
    '3': {'5': 8, '9': 4},
    '4': {'6': 4},
    '5': {'6': 3},
    '6': {},
}

unvisited = {node: None for node in nodes}
visited = {}
current = '1'
currentDistance = 0
unvisited[current] = currentDistance

while True:
    for vertex, distance in distances[current].items():
        if vertex not in unvisited: continue
        newDistance = currentDistance + distance
        if unvisited[vertex] is None or unvisited[vertex] > newDistance:
            unvisited[vertex] = newDistance
    visited[current] = currentDistance
    del unvisited[current]
    if not unvisited: break
    candidates = [node for node in unvisited.items() if node[1]]
    current, currentDistance = sorted(candidates, key=lambda x: x[1])[0]

print(visited)
```


![](img/chema_dijkstra.png)


[Обход в глубину](https://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD) 
